package com.tgy.leetcode;

/**
 * https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
 */
public class _395_至少有K个重复字符的最长子串 {



    public  int longestSubstring(String s, int k) {

        if (s == null || s.length() == 0){

            return 0;
        }

        char[] chars = s.toCharArray();
        return find(chars,0,chars.length - 1,k);
    }

    private  int find(char[] s, int left, int right, int k) {

        if (left > right) {
            return 0;
        }

        int[] sCounts = new int[26];

        for (int i = left; i <= right ; i++) {

            sCounts[s[i] - 'a']++;
        }

        char sep = 0;
        for (int i = left; i <= right ; i++) {

            if (sCounts[s[i] - 'a'] < k) {

                sep = s[i];
                break;
            }
        }

        if (sep == 0) {

            return right - left + 1;
        }

        int res = 0;
        int start = left;
        for (int i = left; i <= right; i++) {

            if (s[i] == sep) {

                res = Math.max(res, find(s, start, i - 1, k));
                start = i + 1;
            }
        }

        res = Math.max(res,find(s,start,right,k));
        return res;
    }

    public static void main(String[] args) {

//        String s = "ababbc";
        String s = "bbaaacbd";
        int k = 2;
        _395_至少有K个重复字符的最长子串 longestSubstring = new _395_至少有K个重复字符的最长子串();
        int res = longestSubstring.longestSubstring(s,k);
        System.out.println(res);
    }
}
